package com.tgy.algorithm.base;


import java.util.HashMap;
import java.util.LinkedList;
import java.util.Stack;

class BiTreeNode {
    int value;
    BiTreeNode left;
    BiTreeNode right;

    BiTreeNode(int value) {
        this.value = value;
    }
}

public class _二叉树的遍历_01 {

    public static BiTreeNode generalBiTreeNode() {

        /**
         *              1
         *        2           3
         *    4      5     6       7
         *
         */
        BiTreeNode root = new BiTreeNode(1);
        root.left = new BiTreeNode(2);
        root.right = new BiTreeNode(3);
        root.left.left = new BiTreeNode(4);
//        root.left.right = new BiTreeNode(5);
        root.right.left = new BiTreeNode(6);
        root.right.right = new BiTreeNode(7);
        return root;
    }

    public static BiTreeNode generalBiTreeNode01() {
        /**
         *                 1
         *              2       3
         *           4     5  6
         *              7       8
         *
         */
        BiTreeNode root = new BiTreeNode(1);
        root.left = new BiTreeNode(2);
        root.right = new BiTreeNode(3);
        root.left.left = new BiTreeNode(4);
        root.left.right = new BiTreeNode(5);
        root.right.left = new BiTreeNode(6);
        root.left.left.right = new BiTreeNode(7);
        root.right.left.right = new BiTreeNode(8);
        return root;
    }

    public static void biTreeInOrder(BiTreeNode root) {
        if (root == null) {
            return;
        }

        Stack<BiTreeNode> stack = new Stack<>();
        BiTreeNode node = root;
        while (!stack.isEmpty() || node != null) {
            if (node != null) {
                stack.push(node);
                node = node.left;
            }else {
                node = stack.pop();
                System.out.println(node.value);
                node = node.right;
            }
        }
    }

    public static void biTreePostOrder(BiTreeNode root) {
        if (root == null) {
            return;
        }

        Stack<BiTreeNode> stack = new Stack<>();
        stack.push(root);
        BiTreeNode preNode = root;
        while (!stack.isEmpty()) {
            BiTreeNode node = stack.peek();
            /**
             *              1
             *        2           3
             *    4      5     6       7
             *
             */
            if (node.left != null && node.left != preNode && node.right != preNode) {
                while (node.left != null) {
                    stack.push(node.left);
                    node = node.left;
                }
            }else if (node.left == preNode && node.right != null) {
                // 左树处理完了，处理右树
                if (node.right != null) {
                    stack.push(node.right);
                }
            }else {
                // node.right == preNode 获取 node == null,说明 node下面的子树都遍历完了，直接遍历根节点
                preNode = stack.pop();
                System.out.println(preNode.value);
            }
        }
    }

    public static void biTreeNodeLevelOrder(BiTreeNode root) {
        if (root == null) {
            return;
        }
        LinkedList<BiTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            BiTreeNode peek = queue.poll();
            System.out.println(peek.value);
            // 先进先出
            if (peek.left != null) {
                queue.offer(peek.left);
            }
            if (peek.right != null) {
                queue.offer(peek.right);
            }
        }
    }


    public static int getMaxLevel(BiTreeNode root) {
        if (root == null) {
            return 0;
        }

//        new HashMap<>()
        /**
         *              1
         *        2           3
         *    4      5     6       7
         *
         */
        // key BiTreeNode,val是key在几层
        HashMap<BiTreeNode, Integer> map = new HashMap<>();
        map.put(root,1);
        int currentLevel = 1;
        int maxLevel= 0;
        int currentLevelCount = 0;
        LinkedList<BiTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            BiTreeNode node = queue.poll();
            // 当前节点在第几层
            int level = map.get(node);
            if(node.left != null) {
                queue.offer(node.left);
                // node.left就是当前节点的下一层
                map.put(node.left, level + 1);
            }

            if (node.right != null) {
                queue.offer(node.right);
                // node.right就是当前节点的下一层
                map.put(node.right,level + 1);
            }

            if (level == currentLevel) {
                currentLevelCount++;
            }else {
                // 下一层开始
                maxLevel = Math.max(maxLevel, currentLevelCount);
                currentLevelCount = 1;
                currentLevel++;
            }
        }

        maxLevel = Math.max(maxLevel, currentLevelCount);
        return maxLevel;
    }

    public static int getMaxLevel01(BiTreeNode root) {

        if (root == null) {
            return 0;
        }


        LinkedList<BiTreeNode> queue = new LinkedList<>();
        queue.offer(root);
        BiTreeNode nextEndNode = null;
        BiTreeNode currentEndNode = root;
        int maxLevel = 0;
        int currentLevelCount = 1;
        while (!queue.isEmpty()) {
            BiTreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
                if (node.right == null) {
                    nextEndNode = node.left;
                }
            }
            if (node.right != null) {
                queue.offer(node.right);
                nextEndNode = node.right;
            }

            if (node != currentEndNode) {
                currentLevelCount++;
            }else {
                // 当前层遍历结束，就可以确定下一行的最后一个节点，下一行在遍历的时候，
                // 没有到达最后一个节点，则一直在当前行计数器加一
                maxLevel = Math.max(maxLevel, currentLevelCount);
                currentLevelCount = 1;
                currentEndNode = nextEndNode;
            }
        }

        return maxLevel;
    }

    public static void main(String[] args) {
        BiTreeNode biTreeNode = generalBiTreeNode();
        BiTreeNode root = generalBiTreeNode01();
//        biTreeInOrder(biTreeNode);
        biTreePostOrder(biTreeNode);
//        biTreeNodeLevelOrder(root);
//        int maxLevel = getMaxLevel01(root);
//        System.out.println(maxLevel);
    }

}
